//
// Created by denglibin on 2020/6/13.
//
// AVL 树， 自平衡二叉查找树
#include <stdio.h>
#include <stdlib.h>
/**
 * 节点-结构
 */
typedef struct node
{
    int data;                       // 数据
    struct node *l_child, *r_child; // 左右子节点
} Node;

/**
 * 左旋
 * @param root
 * @return
 */
static Node *leftRotate(Node *root)
{
    Node *newRoot = root->r_child;            // 右节点作为新的根节点
    Node *rChildLeftChild = newRoot->l_child; // 取出原来右节点的左节点
    newRoot->l_child = root;                  // 原来的根节点作为新的根节点的左节点
    root->r_child = rChildLeftChild;          // 原来根节点的右节点改为新的根节点的左节点
    return newRoot;
}
/**
 * 右旋
 * @param root
 * @return
 */
static Node *rightRotate(Node *root)
{
    Node *newRoot = root->l_child;             // 左节点作为新的根节点
    Node *rChildRightChild = newRoot->r_child; // 取出原来左节点的右节点
    newRoot->r_child = root;                   // 原来的根节点作为新的根节点的右节点
    root->l_child = rChildRightChild;          // 原来根节点的左节点改为新的根节点的右节点
    return newRoot;
}
/**
 * 左右旋
 * @param root
 * @return
 */
static Node *leftRightRotate(Node *root)
{
    Node *newLeft = leftRotate(root->l_child); // 先对root的左子树左旋
    root->l_child = newLeft;

    Node *newRoot = rightRotate(root); // 再对root右旋
    return newRoot;
}
/**
 * 右左旋
 * @param root
 * @return
 */
static Node *rightLeftRotate(Node *root)
{
    Node *newRight = rightRotate(root->r_child); // 对root的右子树右旋
    root->r_child = newRight;

    Node *newRoot = leftRotate(root); // 再对root左旋
    return newRoot;
}
/**
 * 获取树的深度
 * @param root 根节点
 * @param currentDeep 当前遍历的深度
 * @param deep 最终深度的传出参数
 */
static void getDeep(Node *root, int currentDeep, int *deep)
{
    if (!root)
    {
        return;
    }
    if (currentDeep > *deep)
    {
        *deep = currentDeep;
    }
    getDeep(root->l_child, currentDeep + 1, deep);
    getDeep(root->r_child, currentDeep + 1, deep);
}
/**
 * 获取二叉树的深度
 * @param node
 * @return
 */
static int depth(Node *node)
{
    if (node == NULL)
    {
        return 0;
    }
    int depth = 1;
    getDeep(node, 1, &depth);
    return depth;
}
/**
 * 插入数据 出现不平衡时到底是执行LL、RR、LR、RL中的哪一种旋转，取决于插入的位置。可以根据值的大小关系来判断插入的位置。
 * 插入到不平衡节点的右子树的右子树上，自然是要执行LL旋转；
 * 插入到不平衡节点的左子树的左子树上，自然是要执行RR旋转；
 * 插入到不平衡节点的左子树的右子树上，自然是要执行LR旋转；
 * 插入到不平衡节点的右子树的左子树上，自然是要执行RL旋转。
 * @param root
 * @param v
 * @return
 */
static Node *insert(Node *root, int v)
{
    if (root == NULL)
    {
        root = (Node *)calloc(1, sizeof(Node));
        root->data = v;
    }
    else
    {
        if (v < root->data)
        { //插到左子树上
            root->l_child = insert(root->l_child, v);
            if (depth(root->l_child) - depth(root->r_child) >= 2)
            { //左边高右边低
                if (v < root->l_child->data)
                { //右旋 （左子树的左子树）
                    root = rightRotate(root);
                }
                else
                { //先对其左子树左旋再右旋(左右旋) （左子树的右子树）
                    root = leftRightRotate(root);
                }
            }
        }
        else
        { // 插入到右子树上
            root->r_child = insert(root->r_child, v);
            if (depth(root->r_child) - depth(root->l_child) >= 2)
            {
                if (v > root->r_child->data)
                { // 左旋 (右子树的右子树)
                    root = leftRotate(root);
                }
                else
                { // {//先对其右子树右旋再左旋 (右左旋) （右子树的左子树）
                    root = rightLeftRotate(root);
                }
            }
        }
    }
    return root;
}

/**
 * 先序遍历
 * @param root
 */
static void preOrderTraverse(Node *root, int deep)
{
    if (root)
    {
        for (int i = 0; i < deep; i++)
        {
            printf("- ");
        }
        printf("%d\n", root->data);
        preOrderTraverse(root->l_child, deep + 1); // 左 子树
        preOrderTraverse(root->r_child, deep + 1); // 右 子树
    }
}

int main28()
{
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Node *root = NULL;
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        root = insert(root, arr[i]);
    }
    preOrderTraverse(root, 0);
    return 0;
}